#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],sum,ans;
map<pair<pair<int,bool>,pair<int,int>>,int>f;
void chkmax(int &a,int b){a=max(a,b);}
void solve(){
    f.clear();
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i],
        sum+=a[i];
    if (n>2000){cout<<sum/2<<'\n';return;}
    f[{{2,0},{1,0}}]=f[{{2,1},{0,1}}]=(a[1]==a[2]?a[1]:0);
    for (int i=2;i<n;i++){
        int pr0,pr1;
        pr0=i-1;
        for (pr1=0;pr1<i-1;pr1++)
            chkmax(f[{{i+1,0},{i,pr1}}],f[{{i,0},{pr0,pr1}}]+(a[i]==a[i+1]?a[i]:0)),
            chkmax(f[{{i+1,1},{i,pr1}}],f[{{i,0},{pr0,pr1}}]+(a[pr1]==a[i+1]?a[pr1]:0)),
            chkmax(f[{{i+1,0},{pr0,i}}],f[{{i,1},{pr0,pr1}}]+(a[pr0]==a[i+1]?a[pr0]:0)),
            chkmax(f[{{i+1,1},{pr0,i}}],f[{{i,1},{pr0,pr1}}]+(a[i]==a[i+1]?a[i]:0));
        pr1=i-1;
        for (pr0=0;pr0<i-1;pr0++)
            chkmax(f[{{i+1,0},{i,pr1}}],f[{{i,0},{pr0,pr1}}]+(a[i]==a[i+1]?a[i]:0)),
            chkmax(f[{{i+1,1},{i,pr1}}],f[{{i,0},{pr0,pr1}}]+(a[pr1]==a[i+1]?a[pr1]:0)),
            chkmax(f[{{i+1,0},{pr0,i}}],f[{{i,1},{pr0,pr1}}]+(a[pr0]==a[i+1]?a[pr0]:0)),
            chkmax(f[{{i+1,1},{pr0,i}}],f[{{i,1},{pr0,pr1}}]+(a[i]==a[i+1]?a[i]:0));
    }
    for (int i=n,j=0;j<=1;j++){
        int pr0,pr1;
        pr0=i-1;
        for (pr1=0;pr1<i;pr1++) if (pr0!=pr1)
            chkmax(ans,f[{{i,j},{pr0,pr1}}]);
        pr1=i-1;
        for (pr0=0;pr1<i;pr1++) if (pr0!=pr1)
            chkmax(ans,f[{{i,j},{pr0,pr1}}]);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;cin>>T;
    while (T--) solve();
    return 0;
}
